package xyz.sekai52799.offerII;

public class Question13 {
//    地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
//    它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
//    例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
//    请问该机器人能够到达多少个格子？
//
//
//
//    示例 1：
//
//    输入：m = 2, n = 3, k = 1
//    输出：3
//    示例 2：
//
//    输入：m = 3, n = 1, k = 0
//    输出：1
//    提示：
//
//            1 <= n,m <= 100
//            0 <= k<= 20
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public int movingCount(int m, int n, int k) {
        int movingCount = 0;
        int mCount;
        int nCount;
        boolean[][] map = new boolean[m][n];
        map[0][0] = true;

        for (int i = 0;i < m;i++){
            mCount = getNumberSum(i);
            for (int j = 0;j < n;j++){
                nCount = getNumberSum(j);
                if (i == 0 && j > 0 && mCount + nCount <= k){
                    map[i][j] = map[i][j - 1];
                }

                if (i > 0 && j == 0 && mCount + nCount <= k){
                    map[i][j] = map[i - 1][j];
                }

                if (i > 0 && j > 0 && mCount + nCount <= k){
                    map[i][j] = map[i - 1][j] || map[i][j - 1];
                }
            }
        }

        for (int i = 0;i < m;i++){
            for (int j = 0;j < n;j++){
                if (map[i][j]){
                    movingCount++;
                }
            }
        }

        return movingCount;
    }

    public int getNumberSum(int number){
        int result = 0;

        while (number >= 10){
            result = result + (number % 10);
            number = number / 10;
        }
        return result + number;
    }
}
